|
In theoretical computer science, in particular in formal language theory, the Brzozowski derivative ''u''−1''S'' of a set ''S'' of strings and a string ''u'' is defined as the set of all rest-strings obtainable from a string in ''S'' by cutting off its prefix ''u'' (if possible), formally: ''u''−1''S'' = , cf. picture. It is named after the computer scientist Janusz Brzozowski who investigated their properties and gave an algorithm to compute the derivative of a generalized regular expression. ==Derivative of a regular expression== Given a finite alphabet ''A'' of symbols,〔Brzozowski (1964), p.481, required ''A'' to consist of the 2''n'' combinations of ''n'' bits, for some ''n''.〕 a generalized regular expression denotes a possibly infinite set of finite-length strings of symbols from ''A''. It may be built of: * ∅ (denoting the empty set of strings), * ε (denoting the singleton set containing just the empty string), * a symbol ''a'' from ''A'' (denoting the singleton set containing the single-symbol string ''a''), * ''R''∨''S'' (where ''R'' and ''S'' are, in turn, generalized regular expressions; denoting their set's union), * ''R''∧''S'' (denoting the intersection of ''R'' 's and ''S'' 's set), * ¬''R'' (denoting the complement of ''R'' 's set with respect to the set of all strings of symbols from ''A''), * ''RS'' (denoting the set of all possible concatenations of strings from ''R'' 's and ''S'' 's set), * ''R'' * (denoting the set of ''n''-fold repetitions of strings from ''R'' 's set, for any ''n''≥0, including the empty string). In an ordinary regular expression, neither ∧ nor ¬ is allowed. The string set denoted by a generalized regular expression ''R'' is called its language, denoted as ''L''(''R''). As an auxiliary function, δ(''R'') yields the empty string ε if the language corresponding to ''R'' contains ε; otherwise, δ(''R'') yields ∅. This function can be computed by the following rules:〔Brzozowski (1964), p.482, Definition 3.2〕 Based on that, the derivative of a generalized regular expression with respect to a single-symbol string ''a'' can be computed as follows:〔Brzozowski (1964), p.483, Theorem 3.1〕 Finally, for a symbol ''a'', an arbitrary string ''u'', and a generalized regular expression ''R'', the derivative (''ua'')−1''R'' can be computed recursively as ''a''−1(''u''−1''R''); and ε−1''R'' simply equals ''R''.〔Brzozowski (1964), p.483, Theorem 3.2〕 This way, for any given generalized regular expression ''R'' and any string ''u'', the derivative ''u''−1''R'' may be computed as another generalized regular expression.〔Brzozowski (1964), p.483, Theorem 4.1〕 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Brzozowski derivative」の詳細全文を読む スポンサード リンク
|